#include <list>

using namespace std;

// 设计循环双端队列
// 测试链接 : https://leetcode.cn/problems/design-circular-deque/

// 其实内部就是双向链表
// 常数操作慢，但是leetcode数据量太小了，所以看不出劣势
class MyCircularDeque 
{
private:
    list<int> l;
    int limit;

public:
    MyCircularDeque(int k) 
    {
        limit = k;
    }
    
    bool insertFront(int value) 
    {
        if(isFull()) return false;
        l.emplace_front(value);
        return true;
    }
    
    bool insertLast(int value) 
    {
        if(isFull()) return false;
        l.emplace_back(value);
        return true;
    }
    
    bool deleteFront() 
    {
        if(isEmpty()) return false;
        l.pop_front();
        return true;
    }
    
    bool deleteLast() 
    {
        if(isEmpty()) return false;
        l.pop_back();
        return true;
    }
    
    int getFront() 
    {
        if(isEmpty()) return -1;
        return l.front();
    }
    
    int getRear() 
    {
        if(isEmpty()) return -1;
        return l.back();
    }
    
    bool isEmpty() 
    {
        return l.empty();
    }
    
    bool isFull() 
    {
        return l.size() == limit;
    }
};


// 自己用数组实现，常数操作快，但是leetcode数据量太小了，看不出优势
class MyCircularDeque 
{
private:
    int* deq;
    int l, r, sz, limit;

public:
    MyCircularDeque(int k) 
    {
        l = r = sz = 0;
        limit = k;
        deq = new int[k];
    }
    
    bool insertFront(int value) 
    {
        if(isFull()) return false;
        else
        {
            if(isEmpty())
            {
                l = r = 0;
                deq[0] = value;
            }
            else
            {
                l = l == 0 ? (limit - 1) : (l - 1);
                deq[l] = value;
            }
            ++sz;
            return true;
        }
    }
    
    bool insertLast(int value) 
    {
        if(isFull()) return false;
        else
        {
            if(isEmpty())
            {
                l = r = 0;
                deq[0] = value;
            }
            else
            {
                r = (r == limit - 1) ? 0 : (r + 1);
                deq[r] = value;
            }
            ++sz;
            return true;
        }
    }
    
    bool deleteFront() 
    {
        if(isEmpty()) return false;
        else
        {
            l = (l == limit - 1) ? 0 : (l + 1);
            --sz;
            return true;
        }
    }
    
    bool deleteLast() 
    {
        if(isEmpty()) return false;
        else
        {
            r = r == 0 ? (limit - 1) : (r - 1);
            --sz;
            return true;
        }
    }
    
    int getFront() 
    {
        if(isEmpty()) return -1;
        else return deq[l];
    }
    
    int getRear() 
    {
        if(isEmpty()) return -1;
        else return deq[r];
    }
    
    bool isEmpty() 
    {
        return sz == 0;
    }
    
    bool isFull() 
    {
        return sz == limit;
    }
};